package com.xiaoyg.algorithm;

import java.util.HashMap;
import java.util.Map;

public class Quiz {
    // ！！！ 可以根据需要添加另外的函数与变量

    // 数列前2项为 1 1，从第3项开始，若为奇数项，则值为前两项之和，若为偶数项，则值为前两项之和的2倍
    // 可知该数列前6项为 1 1 2 6 8 28
    // 求该数列的第n项
    // 请用递归和循环两种方式实现
    //n = 1 ,f(n) = 1
    //n = 2, f(n) = 1
    //n >= 3 if n%2==0 f(n-2)+f(n -1)
    //n >= 3 if n%2 != 0 2 * ((f(n - 2) + f(n - 1))

    public static void main(String[] args) {
        System.out.println(getN1(6));
        System.out.println(getN2(6));
        System.out.println(getN3(6));

        int array[] = {1, -1 ,3 ,2 ,0};

        System.out.println(getIndex(array));

    }

    public static long getN1(int n) {
        if (n <= 0) {
            return -1;
        }
        if (n == 1) return 1;
        if (n == 2) return 1;
        if (n > 2 && n % 2 == 0) {
            return 2 * (getN1(n - 2) + getN1(n - 1));
        }
        return getN1(n - 2) + getN1(n - 1);
    }

    //备忘录
    public static long getN2(int n) {
        if (n <= 0) return -1;
        Map<Integer, Long> memoMap = new HashMap<>();
        if (n == 1) return 1;
        if (n == 2) return 1;

        if (memoMap.containsKey(n)) {
            return memoMap.get(n);
        }
        long value = 0;
        if (n > 2 && n % 2 == 0) {
            value = 2 * (getN2(n - 2) + getN2(n - 1));
        }
        if (n > 2 && n % 2 != 0) {
            value = getN2(n - 2) + getN2(n - 1);
        }
        //添加备忘录
        memoMap.put(n, value);
        return value;
    }

    //迭代方式
    public static long getN3(int n) {
        if (n <= 0) return -1;
        if (n == 1) return 1;
        if (n == 2) return 1;
        int prePre = 1;
        int pre = 1;
        int temp;
        for (int i = 3; i <= n; i++) {
            if (i % 2 == 0) {
                temp = pre;
                pre = 2 * (pre + prePre);
                prePre = temp;
            } else {
                temp = pre;
                pre = pre + prePre;
                prePre = temp;
            }
        }
        return pre;
    }


    // 给定一个int型数组，找出其中大于0的数字中倒数第二小的数字的下标
    // 例如 1 -1 3 2 0，其中大于0的数字有1 3 2，倒数第二小的数字为2，其下标为3
    // 不能使用排序
    // 尽量只使用一次循环
    public static int getIndex(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        //默认最小值为int最大值，循环比较替换获得最小值
        int min = Integer.MAX_VALUE;
        //第二小数
        int secondMin = Integer.MAX_VALUE;
        //最小小标
        int minIndex = -1;
        //第二小下标
        int secondIndex = -1;

        for (int i = 0; i < array.length; i++) {
            if (array[i] <= 0) {
                continue;
            }
            if (array[i] < min) {
                secondMin = min;
                secondIndex = minIndex;
                min = array[i];
                minIndex = i;
            } else if (array[i] < secondMin && array[i] != min) {
                secondMin = array[i];
                secondIndex = i;
            }
        }
        return secondIndex;
    }
}
